package binaryTree.review;

public class MergeSort2 {

    //归并排序就是后序遍历
    public int[] mergeSort(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        int[] temp = new int[nums.length];
        sort(nums, 0, nums.length - 1, temp);

        return nums;

    }


    public void sort(int[] nums, int lo, int hi, int[] temp) {
        //todo:老是会忘了这个等号
        if (lo >=hi) {
            return;
        }
        int mid = (lo + hi) / 2;
        sort(nums, lo, mid, temp);
        sort(nums, mid + 1, hi, temp);
        merge(nums, lo, mid, hi, temp);
    }

    public void merge(int[] nums, int lo, int mid, int hi, int[] temp) {
        int i = 0;
        int j = lo;
        int k = mid + 1;
        while (j < mid + 1 && k <= hi) {
            if (nums[j] <= nums[k]) {
                temp[i++] = nums[j++];
            } else {
                temp[i++] = nums[k++];
            }
        }
        while (j < mid + 1) {
            temp[i++] = nums[j++];
        }
        while (k <= hi) {
            temp[i++] = nums[k++];
        }

        for (int l = 0; l < i; l++) {
            nums[lo + l] = temp[l];
        }


    }

    public static void main(String[] args) {
        MergeSort2 mergeSort2 = new MergeSort2();
        int[] nums={2,5,3,1};
        int[] ints = mergeSort2.mergeSort(nums);
        for (int a :
                ints) {
            System.out.println(a);

        }
    }


}
